class Solution {
    private:
    bool check(vector<int>&position,int x,int m){
        int pre=0,n=position.size(),cnt=1;
        for(int i=1;i<n;i++){
            if(position[i]-position[pre]>=x){
                pre=i;
                cnt++;
            }
        }
        return cnt>=m;
    }
public:
    int maxDistance(vector<int>& position, int m) {
sort(position.begin(),position.end());
int low=1,high=position.back()-position[0],ans=-1;
while(low<=high){
    int mid=low+(high-low)/2;
    if(check(position,mid,m)){
        ans=mid;
        low=mid+1;
    }
    else high=mid-1;
}
return ans;
    }
};
